package com.gaogzhen.datastructure.tree;

import com.gaogzhen.datastructure.queue.LinkQueue;
import com.gaogzhen.datastructure.queue.Queue;
import com.gaogzhen.datastructure.stack.Stack;
import com.gaogzhen.datastructure.symbolTable.AbstractSortedST;

/**
 * 二叉查找树非递归实现
 *  每个节点存储键值对
 * @author Administrator
 * @version 1.0
 * @description 二叉查找树
 * @date 2022-11-19 21:08
 */
public class BST<K extends Comparable<K>, V> extends AbstractSortedST<K, V> {

    /**
     * 根节点
     */
    private Node<K, V> root;

    /**
     * 内部节点类
     * @param <K>
     * @param <V>
     */
    static class Node<K, V> {
        /**
         * 键
         */
        K key;

        /**
         * 值
         */
        V value;

        /**
         * 左子树
         */
        Node<K, V> left;

        /**
         * 右子树
         */
        Node<K, V> right;

        /**
         * 该节点为根的树中节点总数
         */
        int size;

        Node(K key, V value, Node<K, V> left, Node<K, V> right, int size) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
            this.size = 1;
        }

        Node(K key, V value) {
            this(key, value, null, null, 1);
        }
    }

    /**
     * 获取最小键
     * @return  最小键
     */
    @Override
    public K min() {
        if (isEmpty()) {
            return null;
        }
        Node<K, V> f = null;
        Node<K, V> cur = root;
        while (cur != null) {
            f = cur;
            cur = cur.left;
        }
        return f.key;
    }

    @Override
    public boolean isEmpty() {
        return root == null;
    }

    /**
     * 获取最大键
     * @return  最大键
     */
    @Override
    public K max() {
        if (isEmpty()) {
            return null;
        }
        Node<K, V> f = null;
        Node<K, V> cur = root;
        while (cur != null) {
            f = cur;
            cur = cur.right;
        }
        return f.key;
    }

    /**
     * 向下取整，获取小于给定键的最大键
     * @param key   目标键
     * @return  小于给定键的最大键
     */
    @Override
    public K floor(K key) {
        if (isEmpty()) {
            return null;
        }
        Node<K, V>  cur = root;
        Node<K, V> prev = null;
        while (cur != null) {
            if (key.compareTo(cur.key) < 0) {
                cur = cur.left;
            } else if (key.compareTo(cur.key) > 0) {
                prev = cur;
                cur = cur.right;
            } else {
                return cur.key;
            }
        }
        return prev == null ? null: prev.key;
    }

    /**
     * 向上取整，获取大于给定键的最小值
     * @param key   目标键
     * @return  大于给定键的最小值
     */
    @Override
    public K ceiling(K key) {
        if (isEmpty()) {
            return null;
        }
        Node<K, V>  cur = root;
        Node<K, V> next = null;
        while (cur != null) {
            if (key.compareTo(cur.key) < 0) {
                next = cur;
                cur = cur.left;
            } else if (key.compareTo(cur.key) > 0) {
                cur = cur.right;
            } else {
                return cur.key;
            }
        }
        return next == null ? null: next.key;
    }

    /**
     * 小于key的键的数量
     * @param key    目标key
     * @return  小于key的键的数量
     */
    @Override
    public int rank(K key) {
        if (isEmpty()) {
            return 0;
        }
        Node<K, V>  cur = root;
        int n = 0;
        while (cur != null) {
            if (key.compareTo(cur.key) < 0) {
                cur = cur.left;
            } else if (key.compareTo(cur.key) > 0) {
                n += 1 + (cur.left == null ?  0: cur.left.size);
                cur = cur.right;
            } else {
                break;
            }
        }
        return n;
    }

    /**
     * 返回排序为k的键
     * @param k 排名
     * @return 排序为k的键
     */
    @Override
    public K select(int k) {
        if (isEmpty()) {
            return null;
        }
        int n = k;
        Node<K, V>  cur = root;
        while (cur != null) {
            int nl = cur.left == null ? 0: cur.left.size;
            if (nl  > n) {
                cur = cur.left;
            } else if (nl < n) {
                n = n - nl - 1;
                cur = cur.right;
            } else {
                return cur.key;
            }
        }
        return null;
    }

    /**
     * 删除索引为index的键值对
     * @param index 指定索引
     * @return      要删除键值对中的值
     */
    @Override
    public V delete(int index) {
        return null;
    }

    /**
     * 删除最小的键对应的节点
     * @return  要删除的最小键对应的值
     */
    @Override
    public V deleteMin() {
        if (isEmpty()) {
            // 树为空
            return null;
        }
        // 祖父节点
        Node<K, V> s = null;
        // 父节点
        Node<K, V> f = null;
        // 当前节点
        Node<K, V> cur = root;
        while (cur != null) {
            s = f;
            f = cur;
            cur = cur.left;
        }
        if (s == null) {
            // 根节点为最小键
            root = root.right;
        } else if (f.right == null){
            s.left = null;
        } else {
            s.left = f.right;
        }
        V oldVal = f.value;
        // 清空最小键节点，等待GC
        f.key = null;
        f.value = null;
        f.right = null;
        return oldVal;
    }

    /**
     * 删除最大键对应的键值对
     * @return  最大键对应的值
     */
    @Override
    public V deleteMax() {
        if (isEmpty()) {
            // 树为空
            return null;
        }
        // 祖父节点
        Node<K, V> s = null;
        // 父节点
        Node<K, V> f = null;
        // 当前节点
        Node<K, V> cur = root;
        while (cur != null) {
            s = f;
            f = cur;
            cur = cur.right;
        }
        if (s == null) {
            // 根节点为最小键
            root = root.left;
        } else if (f.left == null){
            s.right = null;
        } else {
            s.right = f.left;
        }
        V oldVal = f.value;
        // 清空最小键节点，等待GC
        f.key = null;
        f.value = null;
        f.left = null;
        return oldVal;
    }

    /**
     * 键[lo,hi]范围内键值对的数量
     * @param lo    范围下限
     * @param hi    范围上限
     * @return      范围内键值对的数量
     */
    @Override
    public int size(K lo, K hi) {
        return 0;
    }

    /**
     * [lo,hi]范围内键的迭代器
     * @param lo    范围下限
     * @param hi    范围上限
     * @return      范围内键的迭代器
     */
    @Override
    public Iterable<K> keys(K lo, K hi) {
        Queue<K> q = new LinkQueue<>();

        Stack<Node<K, V>> l = new Stack<>();
        Node<K, V> current = root;

        while (current != null || !l.isEmpty()) {
            while (current != null) {
                l.push(current);
                current = current.left;
            }
            if (!l.isEmpty()) {
                current = l.pop();
                if (lo.compareTo(current.key) <= 0 && hi.compareTo(current.key) >= 0) {
                    q.offer(current.key);
                }
                current = current.right;
            }
        }

        return q;
    }

    /**
     * 插入键值对，如果key存在则替换旧值；如果不存在，在合适位置插入新的键值对
     * @param key       键
     * @param value     值
     */
    @Override
    public void put(K key, V value) {

        // 判断表是否为空
        if (root == null) {
            root = new Node<>(key, value);
            return;
        }
        // 父节点
        Node<K, V> f = null;
        // 当前节点
        Node<K, V> cur = root;
        // 新插入节点是否为左节点：true-左节点，false-右节点
        boolean left = true;
        // 查找key是否在表中
        while (cur != null) {
            cur.size++;
            if (key.compareTo(cur.key) < 0) {
                // 给定的键小于当前节点的键，继续在左子树查找
                f = cur;
                cur = cur.left;
                left = true;
            } else if (key.compareTo(cur.key) > 0) {
                // 给定的键大于当前节点的键,继续在右子树查找
                f = cur;
                cur = cur.right;
                left = false;
            } else {
                // 给定的键等于当前节点的键,新值替换旧值
                cur.value = value;
                return;
            }
        }
        // key不在表中，插入新节点
        Node<K, V> newNode = new Node<>(key, value);
        if (left) {
            f.left = newNode;
        } else {
            f.right = newNode;
        }
    }

    /**
     * 获取key对应的值
     * @param key   键
     * @return  指定键对应的值
     */
    @Override
    public V get(K key) {
        return get(root ,key);
    }

    /**
     * 从根结点开始查找键对应的值
     * @param node  当前树的根结点
     * @param key   指定的键
     * @return      键对应的值
     */
    private V get(Node<K,V> node, K key) {
        if (node == null) {
            return null;
        }
        Node<K, V>  cur = node;
        while (cur != null) {
            if (key.compareTo(cur.key) < 0) {
                cur = cur.left;
            } else if (key.compareTo(cur.key) > 0) {
                cur = cur.right;
            } else {
                return cur.value;
            }
        }
        return null;
    }

    /**
     * 删除键对应的键值对
     * @param key   键
     * @return      要删除键对应的值
     */
    @Override
    public V delete(K key) {
        if (root == null) {
            return null;
        }
        // 父节点
        Node<K, V>  xp = null;
        // 当前节点
        Node<K, V>  x = root;
        // 路径上的节点
        Stack<Node<K, V>> minus = new Stack<>();
        while (x != null) {
            minus.push(x);
            if (key.compareTo(x.key) < 0) {
                xp = x;
                x = x.left;
            } else if (key.compareTo(x.key) > 0) {
                xp = x;
                x = x.right;
            } else {
                if (x.right != null) {
                    // 查找后继节点
                    Node<K, V> xrp = x;
                    Node<K, V> xr = x.right;
                    while (xr != null) {
                        minus.push(xr);
                        xp = xrp;
                        xrp = xr;
                        xr = xr.left;
                    }
                    // 交换内容
                    K xk = x.key;
                    V xv = x.value;
                    x.key = xrp.key;
                    x.value = xrp.value;
                    xrp.key = xk;
                    xrp.value =xv;
                    x = xrp;
                } else if (x.left != null) {
                    // 查找前驱节点
                    Node<K, V> xlp = x;
                    Node<K, V> xl = x.left;
                    while (xl != null) {
                        minus.push(xl);
                        xp = xlp;
                        xlp = xl;
                        xl = xl.right;
                    }
                    // 交换内容
                    K xk = x.key;
                    V xv = x.value;
                    x.key = xlp.key;
                    x.value = xlp.value;
                    xlp.key = xk;
                    xlp.value =xv;
                    x = xlp;
                }
                // 删除目标节点
                if (xp != null) {
                    if (x.left != null) {
                        if (x == xp.left) {
                            xp.left = x.left;
                        } else {
                            xp.right = x.left;
                        }
                    } else if (x.right != null) {
                        if (x == xp.left) {
                            xp.left = x.right;
                        } else {
                            xp.right = x.right;
                        }
                    } else{
                        if (x == xp.left) {
                            xp.left = null;
                        } else {
                            xp.right = null;
                        }
                    }
                } else {
                    // 树只有一个根节点，删除的节点也是根节点
                    root = null;
                }
                // 记录key对应的值，清空目标节点,等待GC
                V oldVal = x.value;
                x.key = null;
                x.value = null;
                x.left = null;
                x.right = null;
                // 路径上所有节点计数-1
                for (Node<K, V> m : minus) {
                    m.size--;
                }
                return oldVal;
            }
        }
        return null;
    }

    /**
     * 返回结合中键值对的数量
     * @return  键值对的数量
     */
    @Override
    public int size() {
        return isEmpty() ? 0: root.size;
    }

    /**
     * 集合中键的迭代器
     * @return  键的迭代器
     */
    @Override
    public Iterable<K> keys() {
        if (isEmpty()) {
            return null;
        }
        Stack<Node<K, V>> s = new Stack<>();
        Queue<K> q = new LinkQueue<>();
        Node<K, V> x = root;
        while (x != null || !s.isEmpty()) {
            while (x != null) {
                s.push(x);
                x = x.left;
            }
            if (!s.isEmpty()) {
                x = s.pop();
                q.offer(x.key);
                x = x.right;
            }

        }
        return q;
    }
}
